// https://leetcode.cn/problems/minimum-path-sum/

// 算法思路总结：
// 1. 使用一维动态规划优化空间复杂度
// 2. 初始化第一行路径累积和
// 3. 逐行更新最小路径和，取上方和左方最小值
// 4. 时间复杂度：O(mn)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    const int INF = 0x3f3f3f3f;
    int minPathSum(vector<vector<int>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n + 1, INF);
        
        dp[1] = grid[0][0];
        for (int i = 2 ; i <= n ; i++)
            dp[i] = dp[i - 1] + grid[0][i - 1];

        for (int i = 2 ; i <= m ; i++)
            for (int j = 1 ; j <= n ; j++)    
                dp[j] = min(dp[j], dp[j - 1]) + grid[i - 1][j - 1];
        
        return dp[n];
    }
};

int main()
{
    vector<vector<int>> vv1 = {{1,3,1}, {1,5,1}, {4,2,1}};
    vector<vector<int>> vv2 = {{1,2,3}, {4,5,6}};

    Solution sol;

    cout << sol.minPathSum(vv1) << endl;
    cout << sol.minPathSum(vv2) << endl;

    return 0;
}